//简单插入排序

#pragma once

//直接插入排序
template <typename E>
void InsertionSort(E a[], int n)
{
    for(int i = 1; i<n; i++){
        E x = a[i];
        int j = i - 1;
        for(; j >= 0 && x < a[j]; j--)
            a[j + 1] = a[j];
        a[j + 1] = x;
    }
}